public class TXSort {

    public static void main(String[] args) {
        int[] ints = {1, 2, 3, 4, 5, 6, 7, 8};
        sort(ints, 0, ints.length - 1);
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i] + " ");
        }
    }

    /**
     * 1. [left, right] 循环不变量
     * 2. 先从right 开始找一个比tem小的数
     * 3. 再从left 开始找一个比tem大的数
     * 4. 如果 left == right 说明一次循环结束了
     * 5. 由于，对一个本身就有序的数组来说，快排的时间复杂度会降级为n2
     * 6. 为了解决这个问题，拿到一个数组，不管怎么样，先把第一个元素和中间这个元素进行替换，这样时间复杂度就会重新优化到nlogn;
     * @param ints
     * @param left
     * @param right
     */
    public static void sort(int[] ints, int left, int right) {
        int l = left;
        int r = right;
        if (r <= l) {
            return;
        }
        int mid = (r + l) / 2;
        int midValue = ints[mid];
        ints[mid] = ints[left];
        ints[left] = midValue;
        int tem = ints[left];
        while (left < right) {
            while (left < right && tem <= ints[right]) {
                right--;
            }
            while (left < right && ints[left] <= tem) {
                left++;
            }
            if (right > left) {
                int keepValue = ints[left];
                ints[left] = ints[right];
                ints[right] = keepValue;
            }

            if (right == left) {
                tem = ints[l];
                ints[l] = ints[left];
                ints[left] = tem;
                sort(ints, l, left - 1);
                sort(ints, right + 1, r);
                System.out.print("排序完成：");
                for (int i = l; i <= r; i++) {
                    System.out.print(ints[i]);
                    System.out.print(" ");
                }
                System.out.println();
            }
        }
    }
}
